/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-06-24
 * Time: 22:39
 */
//牛客网:https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
//对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Test {
    public static boolean chkPalindrome(ListNode head) {
        if(head==null||head.next==null){
            return true;
        }
        ListNode p1=head;
        ListNode p2=head;
        while(p2!=null&&p2.next!=null){
            p2=p2.next.next;
            p1=p1.next;
        }
        p2=p1.next;
        ListNode last;
        while(p2!=null){
            ListNode p3=p2.next;
            p2.next=p1;
            p1=p2;
            p2=p3;
        }
        last=p1;
        while(head!=last&&head.next!=last){
            if(head.val!=last.val){
                return false;
            }
            head=head.next;
            last=last.next;
        }
        return true;
    }
    public static void main(String[] args) {
        ListNode list1=new ListNode(1);
        ListNode list2=new ListNode(2);
        ListNode list3=new ListNode(2);
        ListNode list4=new ListNode(1);
        list1.next=list2;
        list2.next=list3;
        list3.next=list4;
        System.out.println(chkPalindrome(list1));
    }
}
